#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int countPartitions(vector<int>& nums, int k) {
        int n = nums.size(), mod = 1e9 + 7, sum = 1;
        long long tmp = 0;
        for (auto num : nums) tmp = tmp + num;
        if (tmp < 2 * k) return 0;
        vector<int> dp(k, 0);
        dp[0] = 1;
        for (auto num : nums) {
            sum = (sum + sum) % mod;
            for (int j = k - 1; j >= num; j--) {
                dp[j] = (dp[j] + dp[j - num]) % mod;
            }
        }

        for (auto num : dp) sum = (sum - ((2 * num) % mod) + mod) % mod;
        return sum;
    }
};